<html>
<head><meta charset="utf-8"><title>datafrog-meets-ecs · t-compiler/wg-nll · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/index.html">t-compiler/wg-nll</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html">datafrog-meets-ecs</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="133077498"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077498" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077498">(Aug 30 2018 at 18:31)</a>:</h4>
<p>btw <span class="user-mention" data-user-id="116609">@Frank McSherry</span> one thing I was wanting to ping you about at some point. I was looking at the "hierarchical bit set" crate <a href="https://github.com/slide-rs/hibitset" target="_blank" title="https://github.com/slide-rs/hibitset">hibitset</a> from this "specs" ECS system and it reminded me of datafrog, but using spare bitsets instead of vecs of tuples.</p>



<a name="133077507"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077507" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077507">(Aug 30 2018 at 18:31)</a>:</h4>
<p>we have unfortunately had to suspend work on polonius/datafrog until we can ship the first version of NLL</p>



<a name="133077557"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077557" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077557">(Aug 30 2018 at 18:32)</a>:</h4>
<p>but I've been wondering if we'll hit scalability problems — in some cases we have some awfully large bit sets :)</p>



<a name="133077566"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077566" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077566">(Aug 30 2018 at 18:32)</a>:</h4>
<p>anyway if/when that happens, I was toying with whether we could integrate something like hibitset (or a similar approach) into datafrog...</p>



<a name="133077581"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077581" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077581">(Aug 30 2018 at 18:33)</a>:</h4>
<p>...one of the key operations in ECS being something like "iterate over all entities that have a foo and bar component", basically a JOIN operation</p>



<a name="133077694"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077694" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Frank McSherry <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077694">(Aug 30 2018 at 18:34)</a>:</h4>
<p>There may be a connection. The <a href="https://github.com/HazyResearch/EmptyHeaded" target="_blank" title="https://github.com/HazyResearch/EmptyHeaded">EmptyHeaded</a> folks at Stanford have based a DB on similar algorithmic behavior, but with layout optimizations based on using bitsets for representing dense regions of sparse sets. The hibitset link doesn't have any examples or docs, it seems; do you have another link where you learned more?</p>



<a name="133077820"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077820" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077820">(Aug 30 2018 at 18:36)</a>:</h4>
<p>tbh I've not looked closely at it. I was talking to @Kyrenite (Twitter handle) at RustConf and they were telling me about it</p>



<a name="133077830"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077830" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077830">(Aug 30 2018 at 18:37)</a>:</h4>
<p>from what I understood you have a sort of btree of bitsets</p>



<a name="133077833"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077833" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077833">(Aug 30 2018 at 18:37)</a>:</h4>
<p>and you want to find the intersection quickly</p>



<a name="133077851"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077851" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077851">(Aug 30 2018 at 18:37)</a>:</h4>
<p>so you keep some "fingers" pointing in to them, and when you find that the "next index" from one of the bitsets is ahead of the others, you can skip whole subtrees</p>



<a name="133077856"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077856" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077856">(Aug 30 2018 at 18:37)</a>:</h4>
<p>something something <em>waves hands</em></p>



<a name="133077949"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133077949" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133077949">(Aug 30 2018 at 18:39)</a>:</h4>
<p>anyway NLL is looking closer and closer so I hope that we'll be turning back to polonius in a month or two (maybe faster?)</p>



<a name="133078264"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133078264" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> memoryruins <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133078264">(Aug 30 2018 at 18:44)</a>:</h4>
<p>torkleyy is generally active on the <a href="https://gitter.im/slide-rs/specs" target="_blank" title="https://gitter.im/slide-rs/specs">specs gitter</a> if you want to ask any questions / informal docs</p>



<a name="133078267"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133078267" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> memoryruins <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133078267">(Aug 30 2018 at 18:44)</a>:</h4>
<p>last update i saw was a <a href="https://www.reddit.com/r/rust/comments/8mswjq/what_data_structures_are_not_in_the_std/dzrma3c/" target="_blank" title="https://www.reddit.com/r/rust/comments/8mswjq/what_data_structures_are_not_in_the_std/dzrma3c/">comment they made on reddit</a></p>
<blockquote>
<p>Ah, didn't think that anybody would know hibitset :) I don't work on it very often, so docs and readme aren't very shiny, but the crate itself works. You should note that hibitset is not just a usual bitset, but a multi-layer bitset for a sparse data structures. Currently, we're using 4 layers and that's also the unstable bit of the crate; we want to make the number of layers generic, then I'll stabilize that crate.</p>
</blockquote>



<a name="133078291"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133078291" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Frank McSherry <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133078291">(Aug 30 2018 at 18:45)</a>:</h4>
<p>I've read the comments/docs on hibitset. It looks like a judy array / adaptive radix tree. There are some times when this is good, and some times when it is not great. The HyPer people in Munich have had good luck with ARTs, but you need to engineer them a lot more than it looks like the repo is engineered.</p>



<a name="133079231"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133079231" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133079231">(Aug 30 2018 at 19:02)</a>:</h4>
<p>hmm is there no simd in hibitset ? <span class="emoji emoji-1f914" title="thinking">:thinking:</span></p>



<a name="133079242"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133079242" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133079242">(Aug 30 2018 at 19:03)</a>:</h4>
<p>SIMD all the things</p>



<a name="133079512"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs/near/133079512" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/datafrog-meets-ecs.html#133079512">(Aug 30 2018 at 19:08)</a>:</h4>
<p>I've had such SIMD sorting networks on my todo list of things to try in <span class="emoji emoji-1f438" title="frog">:frog:</span> — the 40y old sorting vs hashing idea, which might be getting interesting with AVX-512 (for DB people and their u64) but for our u32s AVX-2 could be enough <em>whistles</em></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>